package subjectlist;

public class B如何求两个字符串的最长公共子串 {

    public static String getMaxSubStr(String str1, String str2) {

        int len1 = str1.length();
        int len2 = str2.length();

        StringBuilder sb = new StringBuilder("");
        int i, j, max = 0;//max用来记录最长公共字串的长度
        int max1 = 0;//man1用来记录最长公共字串最后一个字符的位置
        //申请新的空间来记录公共子串长度信息
        int[][] M = new int[len1 + 1][len2 + 1];
        for (i = 0; i < len1 + 1; i++) {
            M[i][0] = 0;
        }
        for (j = 0; j < len2 + 1; j++) {
            M[0][j] = 0;
        }
        //通过利用递归公式填写新建的二维驻足（公共子串的长度信息）
        for (i = 1; i < len1 + 1; i++) {
            for (j = 1; j < len2 + 1; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    M[i][j] = M[i - 1][j - 1] + 1;
                    if (M[i][j] > max) {
                        max = M[i][j];
                        max1 = i;
                    }
                } else {
                    M[i][j] = 0;
                }
            }
        }
        for (i = max1 - max; i < max1; i++) {
            sb.append(str1.charAt(i));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String str1 = "abccade";
        String str2 = "dgcadde";
        System.out.println(getMaxSubStr(str1, str2));
        System.out.println(getMaxSubStrSlide(str1, str2));
    }

    public static String getMaxSubStrSlide(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        int i, j;
        int s1begin, s2begin;
        int maxLen = 0, tempMaxLen = 0;
        int maxLenEnd1 = 0;
        StringBuffer sb = new StringBuffer("");
        for (i = 0; i < len1 + len2; i++) {
            s1begin = s2begin = 0;
            tempMaxLen = 0;
            if (i < len1) {
                s1begin = len1 - i;
            } else {
                s2begin = i - len1;
            }
            for (j = 0; (s1begin + j < len1) && (s2begin + j < len2); j++) {
                if (s1.charAt(s1begin + j) == s2.charAt(s2begin + j)) {
                    tempMaxLen++;
                } else {
                    if (tempMaxLen > maxLen) {
                        maxLen = tempMaxLen;
                        maxLenEnd1 = s1begin + j;
                    } else {
                        tempMaxLen = 0;
                    }
                }
            }
            if (tempMaxLen > maxLen) {
                maxLen = tempMaxLen;
                maxLenEnd1 = s1begin + j;
            }
        }
        for (i = maxLenEnd1 - maxLen; i < maxLenEnd1; i++) {
            sb.append(s1.charAt(i));
        }
        return sb.toString();

    }
}
